/*
	file name:delete_list.c
	file object:给定一个链表，删除链表的倒数第n个结点，并且返回链表的头结点
	created time: 2022-03-22
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<unistd.h>
#include<errno.h>
#include<pthread.h>
#include<malloc.h>
#include<stdbool.h>

void sys_err(char* str){
	perror(str);
	exit(1);
}

typedef struct Node{
	int data;
	struct Node* pNext;
}NODE,*PNODE;

PNODE create_list(void);	//创建链表
int length_list(PNODE pHead);	//获取链表长度
void traverse_list(PNODE pHead);	//遍历链表
bool delete_list(PNODE pHead,int back_pos,int* value);	//删除链表结点	
int main(int argc,char* argv[]){
	int * de_val=(int*)malloc(sizeof(int));
	PNODE pHead=NULL;	//初始化一个头指针
	pHead=create_list();	//创建链表
	int back_pos=0;
	printf("The list is following:\n");
	traverse_list(pHead);
	printf("Please input your wanted deleted back_node of list: ");
	scanf("%d",&back_pos);
	if(delete_list(pHead,back_pos,de_val)){
		printf("Delete the node success!\n");
		printf("The deleted num= %d\n",*de_val);
	}else{
		printf("Detele failed!\n");
	}
	printf("The deleted list is followings:\n");
	traverse_list(pHead);
	return 0;
}

PNODE create_list(void){
	int i=0,length=0;
	int value=0;
	PNODE pHead=(PNODE)malloc(sizeof(PNODE));
	if(pHead == NULL){
		printf("Distributed the memory failed!\n");
		printf("Program has exit!\n");
		exit(-1);
	}
	PNODE pTail=pHead;
	pTail->pNext=NULL;
	printf("Please input your wanted length of list: ");
	scanf("%d",&length);

	for(i=0;i<length;i++){
		printf("Please input the value of the %dth node of list:",i+1);
		scanf("%d",&value);
		PNODE pNew=(PNODE)malloc(sizeof(PNODE));
		if(pNew == NULL){
			printf("Distributed the memory failed!\n");
			printf("Program has exit!\n");
			exit(-1);
		}
		pNew->data=value;
		pTail->pNext=pNew;
		pNew->pNext=NULL;
		pTail=pNew;
	}
	return pHead;
}

int length_list(PNODE pHead){
	PNODE p=pHead->pNext;
	int length=0;
	while(p!=NULL){
		length++;
		p=p->pNext;
	}
	return length;
}

void traverse_list(PNODE pHead){
	PNODE p=pHead->pNext;
	while(p!=NULL){
		printf("%d ",p->data);
		p=p->pNext;
	}
	printf("\n");
	return;
}

bool delete_list(PNODE pHead,int back_pos ,int* pVal){
	int i=0;
	PNODE p=pHead;
	int pos=length_list(pHead)-back_pos+1;
	while(p->pNext!=NULL && i<pos-1){
		p=p->pNext;
		i++;
	}

	if(i>pos-1 || p->pNext == NULL)
		return false;
	PNODE q=p->pNext;
	*pVal=q->data;

	p->pNext=p->pNext->pNext;
	free(q);
	q=NULL;

	return true;
}
